GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Polynomialzeit</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Polynomialzeit</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>In der <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">Komplexitätstheorie</a> bezeichnet man ein Problem als in <b>Polynomialzeit</b> lösbar, wenn es mit einer <a href="Turingmaschine" title="Turingmaschine">deterministischen Rechenmaschine</a> in einer Rechenzeit lösbar ist, die mit der Problemgröße nicht stärker als gemäß einer <a href="Polynomfunktion" class="mw-redirect" title="Polynomfunktion">Polynomfunktion</a> wächst.

</p><p>Die Polynomialzeit gilt als eine Grenze zwischen <i>praktisch lösbaren</i> und <i>praktisch nicht lösbaren</i> Problemen. Der Aufwand für Probleme, die nicht in Polynomialzeit lösbar sind, wächst im Allgemeinen so schnell, dass schon relativ kleine Probleme mit verfügbaren Rechnern nicht in überschaubarer Zeit gelöst werden können. Dieser Sachverhalt ist unabhängig vom technologischen Fortschritt, insoweit er die Geschwindigkeit deterministischer Rechner betrifft. Eine Sonderstellung nehmen <a href="Quantencomputer" title="Quantencomputer">Quantencomputer</a> und <a href="DNA-Computer" title="DNA-Computer">DNA-Computer</a> ein, da sie bestimmte nichtdeterministische Operationen ermöglichen.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>Ob ein gegebenes Problem in Polynomialzeit lösbar ist, ist nicht immer von vornherein klar. So wurde für das Problem, zu entscheiden, ob eine gegebene <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürliche Zahl</a> eine <a href="Primzahl" title="Primzahl">Primzahl</a> ist, erst 2002 von Agrawal, Kayal und Saxena ein in Polynomialzeit laufender Algorithmus angegeben (<a href="AKS-Primzahltest" title="AKS-Primzahltest">AKS-Primzahltest</a>). Das naive Verfahren, alle möglichen Teiler durchzuprobieren, ist nicht in Polynomialzeit durchführbar.

</p>

<div class="mw-heading mw-heading2"><h2 id="Formale_Definition">Formale Definition</h2></div>

<p>Ein Problem wird <i>in polynomieller Zeit lösbar</i> genannt, wenn es dafür einen Lösungsalgorithmus gibt, dessen benötigte Rechenzeit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/70b64a27c4f55221162f329285382cc470e3827e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.044ex; height:2.843ex;" alt="{\displaystyle t(n)}" loading="lazy"></span> (z. B. gemessen als Anzahl der Arbeitsschritte einer <a href="Turing-Maschine" class="mw-redirect" title="Turing-Maschine">Turing-Maschine</a>) höchstens polynomiell mit der Größe <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> des Problems (gemessen als Länge der Eingabe für den Lösungsalgorithmus) wächst, wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/70b64a27c4f55221162f329285382cc470e3827e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.044ex; height:2.843ex;" alt="{\displaystyle t(n)}" loading="lazy"></span> die maximale Rechenzeit ist, die der Algorithmus für eine Probleminstanz der Länge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> benötigt. Es existiert ein <a href="Polynom" title="Polynom">Polynom</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span> in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>, das die Rechenzeit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/70b64a27c4f55221162f329285382cc470e3827e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.044ex; height:2.843ex;" alt="{\displaystyle t(n)}" loading="lazy"></span> nach oben beschränkt: für jedes <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(n)\geq t(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(n)\geq t(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b06d68d40d0994122a42771f0b4fb16765c528b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:11.605ex; height:2.843ex;" alt="{\displaystyle p(n)\geq t(n)}" loading="lazy"></span>. Anders gesagt: Es gibt eine <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürliche Zahl</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t\in {\hbox{O}}(n^{k})}">

</mstyle>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t\in {\hbox{O}}(n^{k})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ee9b1bc6c25b275d3a0264c2024ee2f9561baaa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.781ex; height:3.176ex;" alt="{\displaystyle t\in {\hbox{O}}(n^{k})}" loading="lazy"></span> gemäß der <a href="Landau-Notation" class="mw-redirect" title="Landau-Notation">Landau-Notation</a>. Ein solcher Algorithmus heißt <i>Polynomialzeit-Algorithmus</i> oder <i>polynomieller Algorithmus</i> für das Problem.

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiel:_Polynomieller_Algorithmus">Beispiel: Polynomieller Algorithmus</h2></div>

<p>Ein einfaches Verfahren zum Sortieren eines <a href="Feld_(Datentyp)" class="mw-redirect" title="Feld (Datentyp)">Arrays</a> ist das fortwährende Finden und nach hinten Schieben des größten der noch unsortierten Elemente (<a href="Selectionsort" title="Selectionsort">Selectionsort</a>). Der Aufwand dieses Verfahrens ist quadratisch, weil für jedes Element der Eingabe maximal alle anderen Elemente einmal betrachtet werden müssen. Dadurch ergeben sich n+(n-1)+(n-2)... Vergleiche, deren Summe nach dem <a href="Gau%C3%9Fsche_Summenformel" title="Gaußsche Summenformel">kleinen Gauß</a> quadratisch in Abhängigkeit von n wächst. Da eine quadratische Abhängigkeit von der Eingabe polynomiell ist, handelt es sich um einen polynomiellen Algorithmus.

</p>

<div class="mw-heading mw-heading2"><h2 id="Superpolynomialzeit">Superpolynomialzeit</h2></div>

<p>Probleme, deren Berechnungszeit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/70b64a27c4f55221162f329285382cc470e3827e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.044ex; height:2.843ex;" alt="{\displaystyle t(n)}" loading="lazy"></span> mit der Problemgröße <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> stärker als mit einer Polynomfunktion wächst, heißen in <i>Superpolynomialzeit</i> lösbar; ein Beispiel dafür ist exponentielle Zeit, also <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t\in \Omega (c^{n})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t\in \Omega (c^{n})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b1887c8271d4e504878a50767b664179cb480364.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.393ex; height:2.843ex;" alt="{\displaystyle t\in \Omega (c^{n})}" loading="lazy"></span> mit konstantem <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c>1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c>1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bd1d6b5c226641ad3def8e65631f0eb463d9c67a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c>1}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Bezug_zu_den_Komplexitätsklassen"><span id="Bezug_zu_den_Komplexit.C3.A4tsklassen"></span>Bezug zu den Komplexitätsklassen</h2></div>

<p>Die Klasse aller Probleme, die sich auf einer deterministischen sequentiellen Maschine in Polynomialzeit lösen lassen, wird als <i><a href="P_(Komplexit%C3%A4tsklasse)" title="P (Komplexitätsklasse)">P</a></i> (von <i>polynomial</i>) bezeichnet. Die Klasse aller Probleme, die sich von einer <a href="Nichtdeterministische_Turingmaschine" title="Nichtdeterministische Turingmaschine">nichtdeterministischen Maschine</a> in Polynomialzeit lösen lassen, wird als <i><a href="NP_(Komplexit%C3%A4tsklasse)" title="NP (Komplexitätsklasse)">NP</a></i> (von <i>nondeterministic-polynomial time</i>) bezeichnet. Es ist klar, dass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P\subseteq NP}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P\subseteq NP}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9489e234b4f74eb35a304da1c74cdf05bd5993a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.653ex; height:2.343ex;" alt="{\displaystyle P\subseteq NP}" loading="lazy"></span>, also P eine <a href="Mengenlehre" title="Mengenlehre">Teilmenge</a> von NP ist. Eine bis heute unbewiesene Vermutung ist, dass beide Klassen echt verschieden sind, dass also <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P\subsetneq NP}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P\subsetneq NP}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7d96a5602777ba5e1ba98af9af299ae55b4d60a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.653ex; height:2.676ex;" alt="{\displaystyle P\subsetneq NP}" loading="lazy"></span> gilt. Das <a href="P-NP-Problem" title="P-NP-Problem">P-NP-Problem</a> gilt als wichtigstes offenes Problem der <a href="Theoretische_Informatik" title="Theoretische Informatik">theoretischen Informatik</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Kritik">Kritik</h2></div>

<p>Die Polynomialzeit galt bereits in den 1970er Jahren als Grenze zwischen praktisch lösbaren und praktisch unlösbaren Problemen. Diese Abgrenzung ist allerdings für die Praxis nicht trennscharf. Einerseits gibt es auch Methoden mit exponentieller <a href="Worst_Case#Informatik" title="Worst Case">worst-case</a>-Laufzeit, die in der Praxis einsetzbar sind; ein Beispiel hierfür ist der <a href="Simplex-Algorithmus" class="mw-redirect" title="Simplex-Algorithmus">Simplex-Algorithmus</a>. Andererseits wachsen Polynome höheren Grades bereits so schnell, dass viele in Polynomialzeit ablaufende Algorithmen für praktisch vorhandene Problemgrößen dennoch nicht mehr handhabbar sind.

</p><p>Es spricht jedoch eine Reihe von Gründen für die Beibehaltung der Polynomialzeit als „Grenze der Machbarkeit“. Insbesondere gibt es viele Probleme, für die zunächst nur ein hochgradig polynomielles Verfahren bekannt war (dessen Laufzeit durch ein Polynom hohen <a href="Grad_(Polynom)" title="Grad (Polynom)">Grades</a> begrenzt ist), die aber später auch mit niedrigem polynomiellem Aufwand (etwa vom Grad 2 oder 3) gelöst werden konnten.

</p>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Pseudopolynomiell" title="Pseudopolynomiell">Pseudopolynomiell</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text"><span class="cite"><a rel="nofollow" class="external text" href="https://www.nextbigfuture.com/2017/03/computing-exponentially-faster-using-dna.html"><i>Computing exponentially faster using DNA.</i></a> In: <i>next BIG Future.</i> 1. März 2017,<span class="Abrufdatum"> abgerufen am 10. März 2017</span> (englisch).</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3APolynomialzeit&rft.title=Computing+exponentially+faster+using+DNA&rft.description=Computing+exponentially+faster+using+DNA&rft.identifier=https%3A%2F%2Fwww.nextbigfuture.com%2F2017%2F03%2Fcomputing-exponentially-faster-using-dna.html&rft.date=2017-03-01&rft.language=EN"> </span></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-11-21" href="https://de.wikipedia.org/wiki/?title=Polynomialzeit&oldid=250555856">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>